package com.ycz.algorithm.utils.search.binarysearch;

/**
 * @author yancz
 * @ClassName BinarySearchUtil
 * @description: // 二分查找工具类
 * @date 2025-01-28 09:04:43
 * @version: 1.0
 */
public class BinarySearchUtil {

    /*
     * @author yancz
     * @description // 二分查找双闭区间
     * @date 2025/1/28 9:07
     * @param nums 待查找数组
     * @param target 目标值
     * @return int 目标值的索引，不存在返回-1
     */
    public static int binarySearch(int[] nums, int target) {
        int i = 0, j = nums.length - 1; // 初始化值，i=首元素索引，j=尾元素索引
        while (i <= j) {
            // 计算中间值索引
            int mid = i + (j - i) / 2;
            if (nums[mid] < target) { // 目标值在右半部分，即在区间[mid+1,j]中
                i = mid + 1;
            } else if (nums[mid] > target) { // 目标值在左半部分，即在区间[i,mid-1]中
                j = mid - 1;
            } else { // 目标值刚好在中间
                return mid;
            }
        }
        return -1;
    }


    /*
     * @author yancz
     * @description // 二分查找左闭右开区间
     * @date 2025/1/28 11:08
     * @param nums 待查找数组
     * @param target 目标值
     * @return int 目标值的索引，不存在返回-1
     */
    public static int binarySearchLCRO(int[] nums, int target) {
        int i = 0, j = nums.length;
        while (i < j) {
            int mid = i + (j - i) / 2;
            if (nums[mid] < target) {
                i = mid + 1;
            } else if (nums[mid] > target) {
                j = mid;
            } else {
                return mid;
            }
        }
        return -1;
    }

    /*
     * @author yancz
     * @description // 二分查找插入点
     * 给定一个长度为n的有序数组 nums 和一个元素 target ，数组不存在重复元素。
     * 现将 target 插入数组 nums 中，并保持其有序性。若数组中已存在元素 target ，则插入到其左方。请返回插入后 target 在数组中的索引。
     * @date 2025/1/30 11:47
     * @param nums 待插入数组
     * @param target 待插入值
     * @return int 插入之后该值的索引
     */
    public static int binarySearchInsertSimple(int[] nums, int target) {
        int i = 0, j = nums.length - 1; // 初始化双闭区间[0 ,n-1]
        while (i <= j) {
            int mid = i + (j - i) / 2;
            if (nums[mid] < target) { // 目标值在右半部分，即在区间[mid+1,j]中
                i = mid + 1;
            } else if (nums[mid] > target) { // 目标值在左半部分，即在区间[i,mid-1]中
                j = mid - 1;
            } else { // 找到，返回插入点
                return mid;
            }
        }
        return i; // 没有找到，返回插入点i
    }

    /*
     * @author yancz
     * @description // 二分查找插入点，数组存在重复元素，要求返回最左侧找到值的索引
     * @date 2025/3/1 11:36
     * @param nums
     * @param target
     * @return int
     */
    public static int binarySearchInsertHasSame(int[] nums, int target) {
        int i = 0, j = nums.length - 1; // 初始化双闭区间[0 ,n-1]
        while (i <= j) {
            int mid = i + (j - i) / 2; // 计算中间值索引
            if (nums[mid] < target) {
                i = mid + 1;
            } else if (nums[mid] > target) {
                j = mid - 1;
            } else {
                j = mid - 1;
            }
        }
        return i;
    }

    /*
     * @author yancz
     * @description // 查找左边界，在上面的基础上，如果数组中不存在元素，会返回-1，越界超过原数组长度，也需要返回-1
     * @date 2025/3/1 11:47
     * @param nums
     * @param target
     * @return int
     */
    public static int binarySearchLeftEdge(int[] nums, int target) {
        int i = binarySearchInsertHasSame(nums, target);
        if (i == nums.length || nums[i] != target) {
            return -1;
        }
        return i;
    }

    /*
     * @author yancz
     * @description // 查找最右边界
     * @date 2025/3/1 11:53
     * @param nums
     * @param target
     * @return int
     */
    public static int binarySearchRightEdge(int[] nums, int target) {
        int i = binarySearchInsertHasSame(nums, target + 1); // 需要找的是右边界，因此将target+1作为查找值，再将结果减1即可得到右边界
        int j = i - 1;
        if (j == -1 || nums[j] != target) {
            return -1;
        }
        return j;
    }

    public static void main(String[] args) {
        int[] nums = {1, 3, 5, 7, 9, 11, 12, 13, 15, 17, 19};
        int[] nums2 = {1, 3, 5, 7, 9, 11, 12, 13, 13, 13, 13, 15, 17, 19};
        System.out.println("元素9所在索引：" + binarySearch(nums, 9));
        System.out.println("元素17所在索引：" + binarySearch(nums, 17));
        System.out.println("元素18所在索引：" + binarySearch(nums, 18));
        System.out.println("元素9所在索引：" + binarySearchLCRO(nums, 9));
        System.out.println("元素17所在索引：" + binarySearchLCRO(nums, 17));
        System.out.println("元素18所在索引：" + binarySearchLCRO(nums, 18));
        System.out.println("元素13插入后所在索引：" + binarySearchInsertSimple(nums, 13));
        System.out.println("元素13插入后所在索引：" + binarySearchInsertHasSame(nums2, 13));
        System.out.println("元素13左边界索引：" + binarySearchLeftEdge(nums2, 13));
        System.out.println("元素13右边界索引：" + binarySearchRightEdge(nums2, 13));
    }

}
